package cn.cxq.learning.array;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 丑数 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：533511
 * 本题知识点： 数学 二分
 * 算法知识视频讲解
 * 题目描述
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 示例1
 * 输入
 * 复制
 * 7
 * 返回值
 * 复制
 * 8
 */
public class UglyNumber {

    @Test
    public void testUglyNumber() {
        System.out.println(GetUglyNumber_Solution(5));
    }

    //题解：其实就是一个找2^x*3^y*5^z的递正序列的问题（离散值），利用三个指针用来标识2， 3， 5×数组的指针，不断找出其中的最小值就行了。
    public int GetUglyNumber_Solution(int index) {

        if (index == 0) return 0;

        int p2 = 0,p3 = 0,p5 = 0;

        int[] ugly = new int[index];

        ugly[0] = 1;
        int i = 1;

        while (i < index) {

            int min = Math.min(Math.min(ugly[p2] * 2, ugly[p3] * 3), ugly[p5] * 5);

            if (ugly[p2] * 2 == min) {
                p2++;
            } else if (ugly[p3] * 3 == min) {
                p3++;
            } else {
                p5++;
            }

            if (ugly[i-1] != min) ugly[i ++] = min;

        }

        return ugly[index - 1];
    }

    // 自己写的超时了
//    public int GetUglyNumber_Solution(int index) {
//
//        int result = 1;
//
//        for (int num = 0; num < index; result++) {
//            int j = result;
//            while (j != 1) {
//
//                boolean flag = false;
//                if (j / 5 * 5 == j) {
//                    j /= 5;
//                    flag = true;
//                }
//                if (j / 3 * 3 == j) {
//                    j /= 3;
//                    flag = true;
//                }
//
//                if (j / 2 * 2 == j) {
//                    j /= 2;
//                    flag = true;
//                }
//                if (!flag) {
//                    break;
//                }
//            }
//            if (j == 1) {
//                num++;
//            }
//        }
//
//        return --result;
//    }

}
